// https://leetcode.cn/problems/check-if-all-1s-are-at-least-length-k-places-away/?envType=daily-question&envId=2025-11-19

// 算法思路总结：
// 1. 遍历数组记录上一个1出现的位置
// 2. 检查当前1与上一个1之间的距离是否满足要求
// 3. 忽略第一个1之前的距离检查
// 4. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool kLengthApart(vector<int>& nums, int k) 
    {
        int m = nums.size();

        for (int prev = -1, cur = 0 ; cur < m ; cur++)
        {
            if (nums[cur] == 1)
            {
                if (cur - prev - 1 < k && prev != -1)
                {
                    return false;
                }
                prev = cur;
            }
        }

        return true;
    }
};

int main()
{
    vector<int> nums1 = {1,0,0,0,1,0,0,1};
    vector<int> nums2 = {1,0,0,1,0,1};

    int k1 = 2, k2 = 2;

    Solution sol;

    cout << (sol.kLengthApart(nums1, k1) == 1 ? "True" : "False") << endl;
    cout << (sol.kLengthApart(nums2, k2) == 1 ? "True" : "False") << endl;

    return 0;
}